Duyệt cây nhị phân Duyệt cây

Khi xét một cây nhị phân, mỗi đỉnh cùng với các đỉnh đứng sau nó là gốc của một cây con. Ta xét một đỉnh A là đỉnh trong của cây nhị phân. Theo thứ tự người ta xem xét thứ tự thăm đỉnh A so với việc thăm hai con của nó là thăm A trước rồi hai con sau, thăm A xen giữa việc thăm hai con, thăm A sau thi thăm hai con:

  • A, con trái, con phải
  • Con trái, A, con phải
  • Con trái, con phải, A

Tất nhiên nút không có con nào thì việc thăm con không diễn ra. Còn nếu con L hoặc con R của A lại là gốc của một cây con, thì việc thăm thay bằng việc duyệt cây con có gốc tại đó.

Từ đó có các phương pháp duyệt tiền thứ tự, trung thứ tự, hậu thứ tự đối với cây nhị phân có gốc tại đỉnh A như sau

Duyệt tiền thứ tự cây con gốc A

  • Nếu Cây là rỗng Return
  • Thăm A
  • Duyệt tiền thứ tự cây con gốc L
  • Duyệt tiền thứ tự cây con gốc R

Duyệt trung thứ tự cây con gốc A

  • Nếu Cây là rỗng Return
  • Duyệt trung thứ tự cây con gốc L
  • Thăm A
  • Duyệt trung thứ tự cây con gốc R

Duyệt hậu thứ tự cây con gốc A

  • Nếu Cây là rỗng Return
  • Duyệt hậu thứ tự cây con gốc L
  • Duyệt hậu thứ tự cây con gốc R
  • Thăm A